// Copyright 2013 Daniel de Kok
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.gitee.wsl.text.dictomaton.levenshtein

import com.gitee.wsl.collections.list.LinkedList
import com.gitee.wsl.collections.map.TreeMap
import com.gitee.wsl.ext.list.poll

/**
 * State representation of Levenshtein automata.
 */
internal class LevenshteinAutomatonState {
    val transitions: TreeMap<Char, LevenshteinAutomatonState> = TreeMap()
    private var d_final: Boolean
    private var d_recomputeHash: Boolean
    private var d_cachedHash = 0

    /**
     * Construct a state. The state will have no transitions and will be non-final.
     */
    init {
        d_final = false
        d_recomputeHash = true
    }

    /**
     * Add a transition to the state. If a transition with the provided character already
     * exists, it will be replaced.
     *
     * @param c The transition character.
     * @param s The to-state.
     */
    fun addTransition(c: Char, s: LevenshteinAutomatonState) {
        transitions.put(c, s)
        d_recomputeHash = true
    }

    
    override fun hashCode(): Int {
        if (!d_recomputeHash) return d_cachedHash

        val prime = 31
        var result = 1
        result = prime * result + (if (d_final) 1231 else 1237)
        result = prime * result + (if (transitions.isEmpty()) 0 else transitionsHashCode())

        d_recomputeHash = false
        d_cachedHash = result

        return result
    }

    
    override fun equals(obj: Any?): Boolean {
        if (this === obj) return true

        if (obj == null) return false

        if (this::class!= obj::class) return false

        val other = obj as LevenshteinAutomatonState
        if (d_final != other.d_final) return false

        if (transitions.isEmpty()) return other.transitions.isEmpty()

        return transitions == other.transitions
    }

    var isFinal: Boolean
        /**
         * Returns <tt>true</tt> if the state is a final state.
         *
         * @return <tt>true</tt> if the state is a final state, <tt>false</tt> otherwise.
         */
        get() = d_final
        /**
         * Set the 'finalness' of the state.
         *
         * @param finalState If <tt>true</tt>, the state is set to be final. Otherwise, it is non-final.
         */
        set(finalState) {
            d_final = finalState
            d_recomputeHash = true
        }

    /**
     * Obtain the transitions of this state. This method does not return a copy. Modifying the transition
     * map may make the internal state inconsistent.
     *
     * @return The transition map.
     */
//    fun transitions(): TreeMap<Char, LevenshteinAutomatonState> {
//        return transitions
//    }

    /**
     * Follow a transition.
     *
     * @param c The character.
     * @return The target state of the transition, <tt>null</tt> if there is no transition with the given character.
     */
    fun move(c: Char): LevenshteinAutomatonState? {
        return transitions[c]
    }

    /**
     * Reduce the set of outgoing transitions by removing transitions that are also captured by the
     * 'other'-transition. The 'other'-transition are transitions with the given character.
     *
     * @param otherChar The character representing any other character.
     */
    fun reduce(otherChar: Char) {
        val seen = HashSet<Int>()
        val q/*: Queue<LevenshteinAutomatonState?> */= LinkedList<LevenshteinAutomatonState>()
        q.add(this)

        while (!q.isEmpty()) {
            val s = q.poll()
            if (seen.contains(s.hashCode())) continue

            val otherTo: LevenshteinAutomatonState? = s.transitions.get(otherChar)
            if (otherTo == null) {
                // There is no reduction possible in this state: queue the to-states, mark this state
                // as seen and continue with the next state.
                for (toState in s.transitions.values) q.add(toState)

                seen.add(s.hashCode())

                continue
            }

            // Find transitions that can be removed, because they are handled by an 'other' transition. This
            // is the case when a transition is not the 'other' transition, but has the same to-state as the
            // 'other' transition.
            val remove = HashSet<Char>()
            for (trans in s.transitions.entries) if (trans.key != otherChar && trans.value == otherTo)
                remove.add(trans.key)

            // Remove the transitions that were found.
            for (c in remove) s.transitions.remove(c)

            // Recompute the hash if the state table has changed.
            if (remove.isNotEmpty()) s.d_recomputeHash = true

            // We have now seen this state.
            seen.add(s.hashCode())

            // Queue states that can be reached via this state.
            for (toState in s.transitions.values) q.add(toState)
        }
    }

    /**
     * Compute the hashcode for transitions. We do not rely on the[java.util.TreeMap.hashCode],
     * because it will recursively compute the hashcodes of the to-states, which is not necessary since
     * two states are only identical when they have the same symbols leading to exactly the same objects.
     *
     * @return The hashcode of the transition table.
     */
    private fun transitionsHashCode(): Int {
        var hc = 0

        for (e in transitions.entries)
            hc += e.key.hashCode() + e.value.hashCode()

        return hc
    }
}
